import java.util.Arrays;
import java.util.TreeMap;

public class SolutionInterview10_11 {
    public void wiggleSort(int[] nums) {
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }
        for (int i=0;i<nums.length;i++){
            int t;
            if (i%2==0){
                t=map.lastKey();
            }else {
                t=map.firstKey();
            }
            nums[i]=t;
            map.put(t,map.get(t)-1);
            if (map.get(t)==0){
                map.remove(t);
            }
        }
    }

    public static void main(String[] args) {
        int[] ints=new int[]{5,3,1,2,3};
        new SolutionInterview10_11().wiggleSort(ints);
        System.out.println(Arrays.toString(ints));
    }
}
